package Q347

import java.util.*
import kotlin.collections.ArrayList

import java.util.PriorityQueue






class Main {

}

fun main() {
    var num : IntArray = intArrayOf(1,1,1,2,2,3)
    var k = 2
    var topKFrequent = Solution().topKFrequent(num, k)
    for(i in topKFrequent){
        println(i)
    }
}

// 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        var map: MutableMap<Int, Int> = HashMap()

        for (i in nums) {
            map[i] = map.getOrDefault(i, 0) + 1
        }

        var res: IntArray = IntArray(2)
        var list : List<Int> = ArrayList()
        for (i in map.keys) {
            list[i]
        }
        Collections.sort(list)
        var count = 0
        for(i in list.size downTo list.size - k){
            res[count++] = map[i]!!
        }
        return res
    }
}

 class Solution2 {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val result = IntArray(k)
        val map = HashMap<Int, Int>()
        for (num in nums) {
            map[num] = map.getOrDefault(num, 0) + 1
        }
        val entries: Set<Map.Entry<Int, Int>> = map.entries
        // 根据map的value值正序排，相当于一个小顶堆
        val queue = PriorityQueue { o1: Map.Entry<Int, Int>, o2: Map.Entry<Int, Int> -> o1.value - o2.value }
        for (entry in entries) {
            queue.offer(entry)
            if (queue.size > k) {
                queue.poll()
            }
        }
        for (i in k - 1 downTo 0) {
            result[i] = queue.poll().key
        }
        return result
    }
}